package com.leetcode;

import java.util.PriorityQueue;

/**
 * 668. 乘法表中第k小的数
 * 内存溢出了
 *
 * 2022-05-18 每日一题
 *
 * @author fy
 * @date 2022/5/18 8:32
 */
public class Solution668 {

    public int findKthNumber(int m, int n, int k) {
        int mid = m * n / 2;
        PriorityQueue<Integer> priorityQueue;
        if (mid >= k) {
            priorityQueue = new PriorityQueue<>((a, b) -> b - a);
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (priorityQueue.size() < k) {
                        priorityQueue.offer(i * j);
                    } else {
                        if (priorityQueue.peek() > i * j) {
                            priorityQueue.poll();
                            priorityQueue.offer(i * j);
                        }
                    }
                }
            }
        } else {
            priorityQueue = new PriorityQueue<>();
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (priorityQueue.size() < k + 1) {
                        priorityQueue.offer(i * j);
                    } else {
                        if (priorityQueue.peek() < i * j) {
                            priorityQueue.poll();
                            priorityQueue.offer(i * j);
                        }
                    }
                }
            }
        }
        return priorityQueue.peek();
    }


    public static void main(String[] args) {
        int m = 9895;
        int n = 28405;
        int k = 100787757;

        int res = new Solution668().findKthNumber(m, n, k);
        System.out.println(res);
    }

}
